package com.gaogzhen.datastructure.linear;

/**
 * @author Administrator
 * @version 1.0
 * @description 快慢指针查找环路
 * @date 2022-10-19 20:01
 */
public class LinkListCircuitTest {

    public static void main(String[] args) {
        // 创建链表
        Node<String> seven = new Node<>("gg", null);
        Node<String> six = new Node<>("ff", seven);
        Node<String> five = new Node<>("ee", six);
        Node<String> four = new Node<>("dd", five);
        Node<String> three = new Node<>("cc", four);
        Node<String> two = new Node<>("bb", three);
        Node<String> one = new Node<>("aa", two);
        // 环路
        seven.next = three;
        // 判断链表是否有环路
        System.out.println(getEntrance(one).item);

    }

    /**
     * 判断链表是否有环路
     * @param first     头结点
     * @return          是否是环路
     */
    public static boolean isCircuit(Node<String> first) {
        // 定义快慢指针
        Node<String> fast = first;
        Node<String> slow = first;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast == null) {
                break;
            }
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 获取链表环路入口
     * @param first     头指针
     * @return          环路入口节点
     */
    public static Node<String> getEntrance(Node<String> first) {
        // 定义快慢指针，临时指针
        Node<String> fast = first;
        Node<String> slow = first;
        Node<String> temp = null;
        // 遍历链表，先找的环（快慢指针相遇）， 临时指针指向链表的启点，且步长与慢指针一样为1，则慢指针与临时指针相遇的地方就是环的入口
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast == null) {
                break;
            }
            slow = slow.next;
            if (fast == slow) {
                temp = first;
                continue;
            }
            if (temp != null) {
                temp = temp.next;
                if (temp == slow) {
                    return slow;
                }
            }
        }
        return null;
    }

    /**
     * 节点类
     */
    private static class Node<E> {
        E item;
        Node<E> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }
}

